import java.util.Arrays;

public class LeetCode300 {

    /**
     * 计算给定数组中最长递增子序列（Longest Increasing Subsequence, LIS）的长度。
     *
     * @param nums 输入的整数数组
     * @return 最长递增子序列的长度
     */
    public int lengthOfLIS(int[] nums) {
        // 如果输入数组为空，则最长递增子序列长度为0
        if (nums.length == 0) {
            return 0;
        }

        // dp数组，dp[i]表示以nums[i]结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];

        // 初始化dp数组中的所有元素为1，因为每个元素自身可以构成一个长度为1的递增子序列
        Arrays.fill(dp, 1);

        // res变量用于记录当前找到的最长递增子序列的长度，初始值设为1
        int res = 1;

        // 外层循环遍历数组中的每一个元素，从第二个元素开始（i=1）
        for (int i = 1; i < nums.length; i++) {
            // 内层循环遍历当前元素之前的所有元素
            for (int j = 0; j < i; j++) {
                // 如果当前元素nums[i]大于之前的某个元素nums[j]
                if (nums[i] > nums[j]) {
                    // 更新dp[i]为dp[j]+1与当前dp[i]的较大值
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            // 更新结果res为当前找到的最长递增子序列的长度
            res = Math.max(res, dp[i]);
        }

        // 返回最终计算得到的最长递增子序列的长度
        return res;
    }
}